package com.ctrip.demo.leetcode;

import com.sun.org.apache.regexp.internal.RE;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LeetCode720 {

    static int N = 30010, M = 26;
    static int[][] tr = new int[N][M];
    static boolean[] isEnd = new boolean[N];

    static int idx = 0;

    void add(String s) {
        int p = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) {
                tr[p][u] = ++idx;
            }
            p = tr[p][u];
        }
        isEnd[p] = true;
    }

    boolean query(String s) {
        int p = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            p = tr[p][u];
            if (!isEnd[p]) {
                return false;
            }
        }
        return true;
    }

    /**
     *  Trie树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。
     * @param words
     * @return
     */

    public String longestWordByTrie(String[] words) {

        Arrays.fill(isEnd, false);
        for (int i = 0; i <= idx; i++) {
            Arrays.fill(tr[i], 0);
        }
        idx = 0;
        String res = "";
        for (String word : words) {
            add(word);
        }
        System.out.println(Arrays.toString(tr));
        for (String word : words) {
            int n = word.length(), m = res.length();
            if (n < m) {
                continue;
            }
            if (n == m && word.compareTo(res) > 0) {
                continue;
            }
            if (query(word)) {
                res = word;
            }
            System.out.println(res);
        }
        return res;
    }

    public static void main(String[] args) {
        new LeetCode720().longestWordByTrie(new String[]{"a", "banana", "app", "appl", "ap", "apply", "apple"});
    }


    public String longestWord(String[] words) {

        String res = "";
        // 先排序
        Arrays.sort(words);
        System.out.println(Arrays.toString(words));
        // 判断单词是否是拼接而成的
        Set<String> set = new HashSet<>();
        for (String word : words) {
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                res = word.length() > res.length() ? word : res;
                set.add(word);
            }
        }
        System.out.println(res);
        return res;
    }



}
